#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

ListNode* getmid(ListNode* head)
{
    ListNode* slow = head, * fast = head;
    while (fast->next != nullptr && fast->next->next != nullptr)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

ListNode* list_reverse(ListNode* head)
{
    ListNode* cur = head;
    ListNode* nhead = nullptr;
    ListNode* next = nullptr;

    while (cur != nullptr)
    {
        next = cur->next;
        cur->next = nhead;
        nhead = cur;
        cur = next;
    }
    return nhead;
}

void merge(ListNode* l1, ListNode* l2)
{
    ListNode* n1 = l1, * n2 = l2;
    while (l1 != nullptr && l2 != nullptr)
    {
        n1 = l1->next;
        n2 = l2->next;
        l1->next = l2;
        l2->next = n1;
        l1 = n1;
        l2 = n2;
    }
}

void reorderList(ListNode* head) {
    auto mid = getmid(head);
    ListNode* l2 = mid->next;
    mid->next = nullptr;
    l2 = list_reverse(l2);
    merge(head, l2);
}